package com.ting.test.algorithms.贪心算法.最大项目收益;

import java.util.PriorityQueue;

/**
 * 输入: 正数数组costs、正数数组profits、正数K、正数M
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 * K表示你只能串行的最多做k个项目
 * M表示你初始的资金
 * 说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
 * 输出：你最后获得的最大钱数。
 */
public class 最大项目收益 {
    public static void main(String[] args) {
        int[] cost = new int[]{2, 5, 6, 4};//花费
        int[] profits = new int[]{4, 7, 5, 10};//利润

        int K = 3;
        int M = 2;
        int max = fun(cost, profits, K, M);
        System.out.println(max);
    }

    private static int fun(int[] cost, int[] profits, int k, int m) {
        PriorityQueue<Program> costQueue = new PriorityQueue(new MinComparator());
        PriorityQueue<Program> profitsQueue = new PriorityQueue(new MaxComparator());

        //先让花费入小根堆，从小到达开始尝试做项目
        for (int i = 0; i < cost.length; i++) {
            costQueue.add(new Program(cost[i], profits[i]));
        }

        //一共可以做K个项目
        for (int i = 0; i < k; i++) {

            while (!costQueue.isEmpty() && costQueue.peek().cost <= m) {
                //依次弹出当前可以做的所有项目，并进入大根堆
                profitsQueue.add(costQueue.poll());
            }
            //如果大根堆为空，说明当前没有能完成的项目，直接返回
            if (profitsQueue.isEmpty()) {
                return m;
            }
            m += profitsQueue.poll().getProfits();

        }
        return m;
    }
}
